{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Limit of Balls in a Bag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #袋子里最少数目的球"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，其中 <code>nums[i]</code> 表示第 <code>i</code> 个袋子里球的数目。同时给你一个整数 <code>maxOperations</code> 。</p>\n",
    "\n",
    "<p>你可以进行如下操作至多 <code>maxOperations</code> 次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 <strong>正整数</strong> 个球。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>比方说，一个袋子里有 <code>5</code> 个球，你可以把它们分到两个新袋子里，分别有 <code>1</code> 个和 <code>4</code> 个球，或者分别有 <code>2</code> 个和 <code>3</code> 个球。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>你的开销是单个袋子里球数目的 <strong>最大值</strong> ，你想要 <strong>最小化</strong> 开销。</p>\n",
    "\n",
    "<p>请你返回进行上述操作后的最小开销。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [9], maxOperations = 2\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>\n",
    "- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[<strong>9</strong>] -> [6,3] 。\n",
    "- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[<strong>6</strong>,3] -> [3,3,3] 。\n",
    "装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,4,8,2], maxOperations = 4\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,<strong>8</strong>,2] -> [2,4,4,4,2] 。\n",
    "- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,<strong>4</strong>,4,4,2] -> [2,2,2,4,4,2] 。\n",
    "- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,<strong>4</strong>,4,2] -> [2,2,2,2,2,4,2] 。\n",
    "- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,<strong>4</strong>,2] -> [2,2,2,2,2,2,2,2] 。\n",
    "装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [7,17], maxOperations = 2\n",
    "<b>输出：</b>7\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= maxOperations, nums[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-limit-of-balls-in-a-bag](https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-limit-of-balls-in-a-bag](https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9]\\n2', '[2,4,8,2]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        while left < right:\n",
    "            mid = (left+right) >> 1\n",
    "            if sum([(v-1)//mid for v in nums]) > maxOperations:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                if(num % x == 0):\n",
    "                    res += num//x - 1\n",
    "                else:\n",
    "                    res += num//x\n",
    "            return res <= maxOperations\n",
    "        left, right = 1, max(nums)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left < right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            count = 0\n",
    "            for i in nums:\n",
    "                count += (i - 1) // mid\n",
    "            if count <= maxOperations:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        import math\n",
    "        left = 0\n",
    "        right = max(nums) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            value = sum([(x - 1) // mid for x in nums])\n",
    "            if value <= maxOperations:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l, r, ans = 1, max(nums), 0\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            ops = sum((x-1) // mid for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums) + 1\n",
    "\n",
    "        def check(nums, middle, maxOperation):\n",
    "            return sum([(x - 1) // middle for x in nums]) <= maxOperation\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(nums, mid, maxOperations):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(k):\n",
    "            cnt=0\n",
    "            for num in nums:\n",
    "                if k>num:\n",
    "                    continue\n",
    "                cnt=cnt+num//k-int(num%k==0)\n",
    "            print(cnt)\n",
    "            if cnt>maxOperations:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        #check(3)\n",
    "        #return 0\n",
    "\n",
    "        l=1\n",
    "        r=max(nums)\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid)==True:\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        if check(l):\n",
    "            return l \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        # def check(m, k):\n",
    "        #     ans = 0\n",
    "        #     for num in nums:\n",
    "        #         ans += (num-1)//m\n",
    "        #     # print(m,ans)\n",
    "        #     return ans>k\n",
    "        # left = 1\n",
    "        # right = max(nums)\n",
    "        # while left<right:\n",
    "        #     mid = left +(right-left)//2\n",
    "        #     if check(mid, maxOperations):\n",
    "        #         left = mid+1\n",
    "        #     else:\n",
    "        #         right = mid\n",
    "        # return left\n",
    "\n",
    "        l = 1\n",
    "        r = max(nums)\n",
    "        while l<r:\n",
    "            m = (l+r) // 2\n",
    "            if sum([(i-1)//m for i in nums])<=maxOperations:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m+1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l = 1\n",
    "        r = max(nums)\n",
    "        res = max(nums)\n",
    "\n",
    "        def get_op(num_d):\n",
    "            return sum([(x-1)//num_d for x in nums]) <=maxOperations\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if get_op(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                if(num % x == 0):\n",
    "                    res += num//x - 1\n",
    "                else:\n",
    "                    res += num//x\n",
    "            return res <= maxOperations\n",
    "        left, right = 1, max(nums)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(cost):\n",
    "            left_oper = maxOperations\n",
    "            for i in nums:\n",
    "                if i>cost:\n",
    "                    left_oper -=( i//cost if i%cost ==0 else i//cost + 1) - 1\n",
    "            return left_oper>=0\n",
    "\n",
    "\n",
    "        \n",
    "        l,r = 1,max(nums) ##越大越好，答案在右半部分\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        \n",
    "        # 检查最大开销为k，即最终每个袋子都不超过k个球\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                if num <= k:\n",
    "                    continue\n",
    "                quotient = num // k\n",
    "                residue = num % k\n",
    "                if residue == 0:\n",
    "                    count += quotient - 1\n",
    "                else:\n",
    "                    count += quotient\n",
    "                if count > maxOperations:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right +1) = True\n",
    "            if check(mid):\n",
    "                # mid符合，尝试把mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def f(x):\n",
    "            return sum((v - 1) // x for v in nums) <= maxOperations\n",
    "\n",
    "        return bisect_left(range(1, max(nums) + 1), True, key=f) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "\n",
    "        maxcost = right\n",
    "\n",
    "        def check(mid,nums,maxOperations):\n",
    "            op = 0\n",
    "            #遍历袋子里的球数量，如果这个袋子里球数量大于最大开销，就按照最大开销分一下球，看需要操作几次\n",
    "            for i in nums:\n",
    "                if i > mid:\n",
    "                    if i % mid == 0:\n",
    "                        op += int(i / mid) -1\n",
    "                    else:\n",
    "                        op += int(i / mid)\n",
    "\n",
    "            return op<=maxOperations\n",
    "\n",
    "\n",
    "\n",
    "        # 二分可能的最小化最大开销\n",
    "        while left <=right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid,nums,maxOperations):\n",
    "                maxcost = min(maxcost,mid)\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return maxcost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        low=1\n",
    "        high=max(nums)\n",
    "        while low < high:\n",
    "            mid=(low+high)//2\n",
    "            if sum(ceil(n/mid)-1 for n in nums)<=maxOperations:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "\n",
    "        def check(cost):\n",
    "            res = 0\n",
    "            for n in nums:\n",
    "                res += ceil(n/cost) - 1\n",
    "            return res <= maxOperations\n",
    "        \n",
    "        i = 1\n",
    "        j = int(2e9)\n",
    "\n",
    "        while i < j - 1:\n",
    "            mid = (i+j) // 2\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        if check(i):\n",
    "            return i\n",
    "        return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(t: int) -> bool:\n",
    "            cnt = 0\n",
    "            for x in nums:\n",
    "                cnt += (x - 1) // t\n",
    "            return cnt <= maxOperations\n",
    "        \n",
    "        return bisect_left(range(1, max(nums) + 1), True, key=check) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def f(x):\n",
    "            return sum((v - 1) // x for v in nums) <= maxOperations\n",
    "\n",
    "        return bisect_left(range(1, max(nums) + 1), True, key=f) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(nums, l, times):\n",
    "    for x in nums:\n",
    "        if x <= l: continue\n",
    "        if times < 0: return False\n",
    "        times -= (x-1) // l\n",
    "    return times>=0\n",
    "\n",
    "def bs(nums, l, r, times):\n",
    "    if l == r: return r\n",
    "    mid = (l+r) >> 1\n",
    "    if check(nums, mid, times): r = mid\n",
    "    else: l = mid+1\n",
    "    return bs(nums, l, r, times)\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        return bs(nums, 1, max(nums), maxOperations)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l, r = 1, max(nums)\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if sum(math.ceil(n/m)-1 for n in nums if n > m) > maxOperations:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if num > mid:\n",
    "                    cnt += (num - 1) // mid\n",
    "            return cnt <= maxOperations\n",
    "\n",
    "        l, r = 1, max(nums)\n",
    "        return bisect_left(range(r + 1), 1, l, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        #边界 (0, max + 1)\n",
    "        def check(self, nums: List[int], maxOperations: int, m: int):\n",
    "            for num in nums:\n",
    "                maxOperations -= ceil(num / m) - 1\n",
    "                if maxOperations < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        l, r = 0, max(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, nums, maxOperations, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        #边界 (0, max + 1)\n",
    "        def check(self, nums: List[int], maxOperations: int, m: int):\n",
    "            for num in nums:\n",
    "                maxOperations -= ceil(num / m) - 1\n",
    "                if maxOperations < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        l, r = 0, max(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, nums, maxOperations, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l, r = 1, max(nums)\n",
    "        n = len(nums)\n",
    "        def check(x):\n",
    "            res = sum(map(lambda y: 0 if y <= x else ceil(y / x) - 1, nums))\n",
    "            return res <= maxOperations\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid): r = mid\n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                cnt += (num - 1) // x\n",
    "                if cnt > maxOperations:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        left, right = 1, max(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        right = max(nums)\n",
    "        left = 0\n",
    "        output = 0\n",
    "        totalNum = sum(nums)\n",
    "        finalBag = maxOperations + len(nums)\n",
    "        if totalNum % finalBag == 0:\n",
    "            left = totalNum // finalBag\n",
    "        else:\n",
    "            left = totalNum // finalBag + 1\n",
    "\n",
    "        while left <= right:\n",
    "            m = (left + right) // 2\n",
    "            countDev = 0\n",
    "            for i in nums:\n",
    "                countDev += (i - 1) // m\n",
    "            if countDev <= maxOperations:\n",
    "                output = m\n",
    "                right = m - 1\n",
    "            else:\n",
    "                left = m + 1\n",
    "            \n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        right = max(nums)\n",
    "        left = 0\n",
    "        output = 0\n",
    "        totalNum = sum(nums)\n",
    "        finalBag = maxOperations + len(nums)\n",
    "        if totalNum % finalBag == 0:\n",
    "            left = totalNum // finalBag\n",
    "        else:\n",
    "            left = totalNum // finalBag + 1\n",
    "\n",
    "        while left <= right:\n",
    "            m = (left + right) // 2\n",
    "            countDev = 0\n",
    "            for i in nums:\n",
    "                countDev += (i - 1) // m\n",
    "            if countDev <= maxOperations:\n",
    "                output = m\n",
    "                right = m - 1\n",
    "            else:\n",
    "                left = m + 1\n",
    "            \n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l,r = 0,max(nums)\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            for x in nums:\n",
    "                if x > mid:\n",
    "                    cnt += (x + mid - 1)//mid - 1\n",
    "                    if cnt > maxOperations:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left,right = 1,max(nums)\n",
    "        ans = 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            opt = sum((num-1)//mid for num in nums)\n",
    "            if opt <= maxOperations:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l, r = 1, max(nums)\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if sum((n-1)//m for n in nums if n > m) > maxOperations:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "\n",
    "        def check(target):\n",
    "            sum_=0\n",
    "\n",
    "            for i in nums:\n",
    "                sum_+=(i-1)//target\n",
    "\n",
    "            if sum_<=maxOperations:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return bisect_left(range(1,max(nums)+1),True,key=check)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right, ans = 1, max(nums), 0\n",
    "        while left <= right:\n",
    "            y = (left + right) // 2\n",
    "            ops = sum((x - 1) // y for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = y\n",
    "                right = y - 1\n",
    "            else:\n",
    "                left = y + 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(target):\n",
    "            op = 0\n",
    "            for num in nums:  # 直接均分,根据组数统计op\n",
    "                op += (num-1)//target\n",
    "            return op <= maxOperations\n",
    "\n",
    "        low = 1\n",
    "        high = max(nums)\n",
    "        while low < high:\n",
    "            mid = (low+high)//2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right, ans = 1, max(nums), 0\n",
    "        while left <= right:\n",
    "            y = (left + right) // 2\n",
    "            ops = sum((x - 1) // y for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = y\n",
    "                right = y - 1\n",
    "            else:\n",
    "                left = y + 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        l, r, ans = 1, max(nums), 0\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            ops = sum((x-1) // mid for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(n):\n",
    "            t = maxOperations\n",
    "            for v in nums:\n",
    "                # if v<n:\n",
    "                #     return False\n",
    "                if v >n:\n",
    "                    div = math.ceil(v/n)\n",
    "                    t -=(div-1)\n",
    "                    if t<0:\n",
    "                        return False\n",
    "            return True\n",
    "                \n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left<=right:\n",
    "            mid = left +(right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        output = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            ops = sum((x - 1) // mid for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                output = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            if m == 0:\n",
    "                return False\n",
    "            s = 0\n",
    "            for x in nums:\n",
    "                s += (x + m - 1) // m - 1\n",
    "                if s > maxOperations:\n",
    "                    return False\n",
    "            return True\n",
    "        left = 0\n",
    "        right = max(nums) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        total = sum(nums)\n",
    "\n",
    "        def cal_oper(val):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if num > val:\n",
    "                    cnt += num // val - 1\n",
    "                    if num % val != 0:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        \n",
    "        left, right = 1, total\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            val = cal_oper(mid)\n",
    "            if val > maxOperations:\n",
    "                left = mid + 1\n",
    "            elif val <= maxOperations:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right, ans = 1, max(nums), 0\n",
    "        while left <= right:\n",
    "            y = (left + right) // 2\n",
    "            ops = sum((x - 1) // y for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = y\n",
    "                right = y - 1\n",
    "            else:\n",
    "                left = y + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right, ans = 1, max(nums), 0\n",
    "        while left<=right:\n",
    "            y = (left+right) // 2\n",
    "            ops = sum((x-1)//y for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = y\n",
    "                right = y-1\n",
    "            else:\n",
    "                left = y+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: list[int], maxOperations: int) -> int:\n",
    "        def check(n):\n",
    "            ans=0\n",
    "            for num in nums:\n",
    "                ans+=math.ceil(num/n)-1\n",
    "            return ans<=maxOperations\n",
    "        left=1\n",
    "        right = max(nums)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left= mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        l, r = 1, max(nums)\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            # 如果可以在最大操作数内完成 就可以再最小化最大值\n",
    "            # 即把右边界左移\n",
    "            if check(nums, maxOperations, mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "# 小于等于返回True\n",
    "def check(nums, maxOperations, maxBall):\n",
    "    cnt = 0\n",
    "    for i in nums:\n",
    "        if i > maxBall:\n",
    "            cnt += ceil(i / maxBall) - 1\n",
    "    print('cnt', cnt)\n",
    "    return cnt <= maxOperations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(k):\n",
    "            cnt=0\n",
    "            for num in nums:\n",
    "                if k>num:\n",
    "                    continue\n",
    "                cnt=cnt+num//k-int(num%k==0)\n",
    "            #print(cnt)\n",
    "            if cnt>maxOperations:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        #check(3)\n",
    "        #return 0\n",
    "\n",
    "        l=1\n",
    "        r=max(nums)\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid)==True:\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        if check(l):\n",
    "            return l \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        #边界 (0, max + 1)\n",
    "        def check(self, nums: List[int], maxOperations: int, m: int):\n",
    "            for num in nums:\n",
    "                maxOperations -= ceil(num / m) - 1\n",
    "                if maxOperations < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        l, r = 0, max(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, nums, maxOperations, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def f(x):\n",
    "            return sum((v - 1) // x for v in nums) <= maxOperations\n",
    "\n",
    "        return bisect_left(range(1, max(nums) + 1), True, key=f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right-left)//2\n",
    "            total = 0\n",
    "            for i in nums:\n",
    "                if i % mid == 0:\n",
    "                    total += i // mid - 1\n",
    "                else:\n",
    "                    total += i // mid\n",
    "\n",
    "            if total > maxOperations:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "            \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def valid(max_v):\n",
    "            cnt = 0\n",
    "            for v in nums:\n",
    "                cnt += (v - 1) // max_v\n",
    "                if cnt > maxOperations:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        l, r = 1, max(nums)\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if valid(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        right = max(nums)\n",
    "        left = 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            count = 0\n",
    "            condition = False\n",
    "            for num in nums:\n",
    "                count += (num - 1)// mid\n",
    "                if count > maxOperations:\n",
    "                    condition = True\n",
    "                    break\n",
    "            \n",
    "            if condition:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        \n",
    "        # 检查最大开销为k，即最终每个袋子都不超过k个球\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                # if num <= k:\n",
    "                #     continue\n",
    "                quotient = num // k\n",
    "                residue = num % k\n",
    "                if residue == 0:\n",
    "                    count += quotient - 1\n",
    "                else:\n",
    "                    count += quotient\n",
    "                if count > maxOperations:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right +1) = True\n",
    "            if check(mid):\n",
    "                # mid符合，尝试把mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        \n",
    "        # 检查最大开销为k，即最终每个袋子都不超过k个球\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                # if num <= k:\n",
    "                #     continue\n",
    "                quotient = num // k\n",
    "                residue = num % k\n",
    "                if residue == 0:\n",
    "                    count += quotient - 1\n",
    "                else:\n",
    "                    count += quotient\n",
    "                if count > maxOperations:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right +1) = True\n",
    "            if check(mid):\n",
    "                # mid符合，尝试把mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right, ans = 1, max(nums), 0\n",
    "        while left <= right:\n",
    "            y = (left + right) // 2\n",
    "            ops = sum((x - 1) // y for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = y\n",
    "                right = y - 1\n",
    "            else:\n",
    "                left = y + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        right = max(nums)\n",
    "        left = 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            count = 0\n",
    "            condition = False\n",
    "            for num in nums:\n",
    "                if num % mid == 0:\n",
    "                    count += num // mid - 1\n",
    "                else:\n",
    "                    count += num // mid\n",
    "                if count > maxOperations:\n",
    "                    condition = True\n",
    "                    break\n",
    "            \n",
    "            if condition:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        def check(c, maxOperations):\n",
    "            for x in nums:\n",
    "                if x <= c:\n",
    "                    break\n",
    "                maxOperations -= (x - 1) // c\n",
    "                if maxOperations < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        a, b = 1, nums[0]\n",
    "        while a < b:\n",
    "            c = a + (b - a) // 2\n",
    "            if check(c, maxOperations):\n",
    "                b = c\n",
    "            else:\n",
    "                a = c + 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            valid = True\n",
    "            op = 0\n",
    "            for x in nums:\n",
    "                op += (x-1) // mid\n",
    "                if op > maxOperations:\n",
    "                    valid = False\n",
    "                    break\n",
    "            if valid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        def check(x):\n",
    "            cnt=0\n",
    "            for y in nums:\n",
    "                if y<=x:continue\n",
    "                # 1倍以下0次\n",
    "                # 2倍1次\n",
    "                # 1.5倍1次\n",
    "                if y%x==0:\n",
    "                    cnt+=y//x-1\n",
    "                else:\n",
    "                    cnt+=y//x\n",
    "            return cnt<=maxOperations\n",
    "        l,r=1,max(nums)\n",
    "        while l<r:\n",
    "            m=l+r>>1\n",
    "            if check(m):\n",
    "                r=m \n",
    "            else:\n",
    "                l=m+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumSize(self, nums, maxOperations: int) -> int:\r\n",
    "        def check(m):\r\n",
    "            t = 0\r\n",
    "            for n in nums:\r\n",
    "                if n > m:\r\n",
    "                    t += math.ceil((n-m)/m)\r\n",
    "            if t > maxOperations:\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return True \r\n",
    "        low = math.ceil(sum(nums)/(maxOperations+len(nums)))\r\n",
    "        high = max(nums) + 1\r\n",
    "        while low < high:\r\n",
    "            mid = (low+high)//2\r\n",
    "            if not check(mid):\r\n",
    "                low = mid + 1\r\n",
    "            else:\r\n",
    "                high = mid\r\n",
    "        return low \r\n",
    "\r\n",
    "# print(Solution().minimumSize([9], 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        # 最小化最大值，二分答案处理\n",
    "        def f(x):\n",
    "            if x == 0:\n",
    "                return False\n",
    "            cnt = sum(ceil(max(0, v-x) / x) for v in nums)\n",
    "            return cnt <= maxOperations\n",
    "\n",
    "\n",
    "        return bisect_left(range(max(nums)+1), True, key=f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq  \n",
    "class Solution:\n",
    "    def minimumSize(self, nums, m: int):\n",
    "        l = 1\n",
    "        r = max(nums)\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            def check(c):\n",
    "                ans = 0\n",
    "                for n in nums:\n",
    "                    if n % c == 0:\n",
    "                        ans += n//c - 1\n",
    "                    else:\n",
    "                        ans += n//c  \n",
    "                return ans <= m\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        left, right, ans = 1, max(nums), 0\n",
    "        while left <= right:\n",
    "            y = (left + right) // 2\n",
    "            ops = sum((x - 1) // y for x in nums)\n",
    "            if ops <= maxOperations:\n",
    "                ans = y\n",
    "                right = y - 1\n",
    "            else:\n",
    "                left = y + 1     \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumSize(self, nums, maxOperations: int) -> int:\r\n",
    "        def check(m):\r\n",
    "            t = 0\r\n",
    "            for n in nums:\r\n",
    "                if n > m:\r\n",
    "                    t += math.ceil((n-m)/m)\r\n",
    "            if t > maxOperations:\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return True \r\n",
    "        low = math.ceil(sum(nums)/(maxOperations+len(nums)))\r\n",
    "        high = max(nums) + 1\r\n",
    "        while low < high:\r\n",
    "            mid = (low+high)//2\r\n",
    "            if not check(mid):\r\n",
    "                low = mid + 1\r\n",
    "            else:\r\n",
    "                high = mid\r\n",
    "        return low \r\n",
    "\r\n",
    "# print(Solution().minimumSize([9], 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumSize(self, nums, maxOperations: int) -> int:\r\n",
    "        def check(m):\r\n",
    "            t = 0\r\n",
    "            for n in nums:\r\n",
    "                if n > m:\r\n",
    "                    t += math.ceil((n-m)/m)\r\n",
    "            if t > maxOperations:\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return True \r\n",
    "        low = 1\r\n",
    "        high = max(nums) + 1\r\n",
    "        while low < high:\r\n",
    "            mid = (low+high)//2\r\n",
    "            if not check(mid):\r\n",
    "                low = mid + 1\r\n",
    "            else:\r\n",
    "                high = mid\r\n",
    "        return low \r\n",
    "\r\n",
    "# print(Solution().minimumSize([9], 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumSize(self, nums, maxOperations: int) -> int:\r\n",
    "        def check(m):\r\n",
    "            t = 0\r\n",
    "            for n in nums:\r\n",
    "                if n > m:\r\n",
    "                    t += math.ceil((n-m)/m)\r\n",
    "            if t > maxOperations:\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return True \r\n",
    "        low = 1\r\n",
    "        high = max(nums) + 1\r\n",
    "        while low < high:\r\n",
    "            mid = (low+high)//2\r\n",
    "            if not check(mid):\r\n",
    "                low = mid + 1\r\n",
    "            else:\r\n",
    "                high = mid\r\n",
    "        return low \r\n",
    "\r\n",
    "# print(Solution().minimumSize([9], 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSize(self, nums: List[int], maxOperations: int) -> int:\n",
    "        # 二分答案，最小的最大值\n",
    "        maxv = max(nums)\n",
    "\n",
    "        def check(k):\n",
    "            cot = 0\n",
    "            for num in nums:\n",
    "                if num>k:\n",
    "                    if num%k==0:\n",
    "                        cot += ((num//k)-1)\n",
    "                    else:\n",
    "                        cot += (num//k)\n",
    "            return cot<=maxOperations\n",
    "\n",
    "        l,r = 1,maxv\n",
    "        ans = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
